package 剑指offer;

/**
 * @author zhangmin
 * @create 2021-11-23 9:22
 * 双指针
 */
public class day13_21_57_581 {

    /**===========================================================================================================================
     * 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
     * 双指针：left指着前半部分中需要交换到后面的偶数，right指着后半部分中需要交换到前面的奇数
     * */
    public int[] exchange(int[] nums) {
        int n=nums.length;
        int left=0,right=n-1;
        while (left<right){
            if (nums[left]%2==0&&nums[right]%2==1){
                //刚好left时偶数，right时奇数，两者交换
                int t=nums[left];
                nums[left]=nums[right];
                nums[right]=t;
                left++;right--;
            }else if (nums[left]%2==1){
                //left为奇数，left指针后移
                left++;
            }else if (nums[right]%2==0){
                //right为偶数，right指针前移
                right--;
            }
        }
        return nums;
    }

    /**===========================================================================================================================
     * 剑指 Offer 57. 和为s的两个数字
     * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
     * 1、用set存已经出现的数字，遍历数组，对每个元素i找target-nums[i]是否存在即可。
     * 2、双指针，对撞指针一头一尾交替前进
     * 3、二分查找，对每个元素，通过二分查找是否存在target-nums[i]即可
     * */
    public int[] twoSum(int[] nums, int target) {
        int n=nums.length;
        int left=0,right=n-1;
        while (left<right){
            int sum = nums[left] + nums[right];
            if (sum ==target) return new int[]{nums[left],nums[right]};
            else if (sum<target){
                left++;
            } else if (sum>target){
                right--;
            }
        }
        return new int[]{-1,-1};
    }

    /**===========================================================================================================================
     * 剑指 Offer 58 - I. 翻转单词顺序
     * 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
     * */
    public String reverseWords(String s) {
        if (s.length()==0) return "";
        String[] sl = s.split(" ");
        if (sl.length==0) return "";
        StringBuffer sb=new StringBuffer();
        for (int i = sl.length-1; i >=0 ; i--) {
            System.out.println(i+"="+sl[i]+sl[i].length());
            if (sl[i].length()!=0){
                sb.append(sl[i]);
                sb.append(" ");
            }
        }
        String res=sb.toString();
        return res.substring(0,res.length()-1);
    }

    public static void main(String[] args) {
        day13_21_57_581 obj=new day13_21_57_581();
        System.out.println(obj.reverseWords( " "));
    }
}
